1. Field of the Invention
The present invention pertains to a scheduler, a scheduling method, a scheduling program and a high-level synthesis apparatus for automatically synthesizing a logic circuit from behavioral descriptions.
2. Description of the Related Art
The scale of a system which can be mounted on one chip has increased as semiconductor technology develops. For this reason, a high-level synthesis methodology as a means for designing a large-scale system in a short period of time is disclosed in “HIGH-LEVEL SYNTHESIS Introduction to Chip and System Design”, Daniel D. Gajski et al., Kluwer Academic Publishers, 1992, and is further disclosed in Japanese patent Laid Open Publication (Kokai) No. H05-101141. The high-level synthesis methodology synthesizes Register Transfer Level (RTL) descriptions including hardware information, such as clock cycles, a register, an arithmetic unit and the like, from behavioral descriptions describing only operations of the system.
In the high-level synthesis, the process for partitioning the analyzed behavioral descriptions into groups to execute in each clock cycle (cycle of operation) is called “scheduling”, and each clock cycle is called “control step”.
The behavioral descriptions may have a hierarchical structure depending on the design. For example, behavioral descriptions described by using C programming language may have a hierarchical structure including function calls. In this case, the side for calling functions belongs an upper-hierarchy, and the called functions belong a lower-hierarchy.
In the conventional scheduling method, each operation described in the behavioral descriptions is assigned to any control step only based on a delay value and the number of the control steps required for execution of the operation. Therefore, the operation to be scheduled is scheduled into a control step after a control step in which an operation calculating input data of the operation to be scheduled was scheduled. Furthermore, an operation using output data of the operation to be scheduled will be scheduled into a control step after the control step in which the operation to be scheduled is scheduled.
The function belonging to the lower-hierarchy is similarly scheduled only based on a delay and the number of the control steps required for execution of the function. Therefore, the function is scheduled so that: execution of the function belonging to the lower-hierarchy is started after all input data to pass to the function belonging to the lower-hierarchy is available; and output data from the function can be used in the upper-hierarchy after execution of the function belonging to the lower-hierarchy is perfectly completed.
In the above scheduling method, since it was not enough considered that the fact of the matter is that parallel execution is possible between the upper-hierarchy and the lower-hierarchy, there was a problem that the optimum scheduling is impossible.
Similarly, in the case that two or more functions belonging to the lower-hierarchy are called from the upper-hierarchy side, it was also not enough considered that the fact of the matter is that each function belonging to the lower-layer is executable in parallel. Therefore, there was also a problem that it is scheduled in series so that execution of the function called second is started after execution of the function called first is completed.
Moreover, in the conventional scheduling method by in-lining the behavioral descriptions of the lower-hierarchy into the behavioral descriptions of the upper-hierarchy, there was the constraint that the behavioral descriptions of the lower-hierarchy had to be prepared beforehand. Therefore, there was also a problem that design was not fully reusable.